# def merge_sort(nums):
#     def merge(lst1,lst2):
#         if len(lst1)==0: return lst2
#         if len(lst2)==0: return lst1 
#         if lst1[0]<=lst2[0]: 
#             return [lst1[0]]+merge(lst1[1:],lst2)
#         else:
#             return [lst2[0]]+merge(lst1,lst2[1:])
        
#     n=len(nums)
#     if n<=1: return nums 
#     mid=n//2 #**
#     left=merge_sort(nums[:mid])
#     right=merge_sort(nums[mid:])
#     return merge(left,right)

# def quick_sort(nums):
#     def partition(nums,l,r):
#         p=l
#         i,j=p+1,p+1 
#         while j<=r:
#             if nums[j]<nums[p]:
#                 nums[i],nums[j]=nums[j],nums[i]
#                 i+=1 
#             j+=1 
#         part=i-1 #**
#         nums[part],nums[p]=nums[p],nums[part]
#         return part 
    
#     def sort_main(nums,l,r):
#         if l<r:
#             part = partition(nums,l,r)
#             sort_main(nums,l,part-1)
#             sort_main(nums,part+1,r)
#         return nums 
    
#     return sort_main(nums,0,len(nums)-1)
        

def merge_sort(nums):   
    def merge(lst1,lst2):
        if len(lst1)==0: return lst2 
        if len(lst2)==0: return lst1 
        if lst1[0]<=lst2[0]:
            return [lst1[0]]+merge(lst1[1:],lst2)
        return [lst2[0]]+merge(lst1,lst2[1:])
    
    n = len(nums)
    if n<=1: return nums
    lst1 = merge_sort(nums[:n//2])
    lst2 = merge_sort(nums[n//2:])
    return merge(lst1,lst2)
    

# def quick_sort(nums):
#     def partition(nums,l,r):
#         p = l 
#         i,j = l+1,l+1 
#         while j<=r:
#             if nums[j]<nums[p]:
#                 nums[i],nums[j] = nums[j],nums[i]
#                 i+=1 
#             j+=1 
#         part = i-1 #***
#         nums[p],nums[part] = nums[part],nums[p]
#         return part
    
#     def core(nums,l,r):
#         if l<r: #***
#             part = partition(nums,l,r)
#             core(nums,l,part-1)
#             core(nums,part+1,r)

#     core(nums,0,len(nums)-1)
#     return nums



def quick_sort(nums):
    def partition(nums,l,r):
        p = l 
        i,j = l+1,l+1 
        while j<=r:
            if nums[j]<nums[p]:
                nums[i],nums[j] = nums[j],nums[i]
                i+=1 
            j+=1 
        part = i-1 
        nums[p],nums[part] = nums[part],nums[p]
        return part 
    
    def core(nums,l,r):
        if l<r:
            p = partition(nums,l,r)
            core(nums,l,p-1)
            core(nums,p+1,r)

    core(nums,0,len(nums)-1)
    return nums



nums=[1,3,2,5,7,9,6]
print(merge_sort(nums))
print(quick_sort(nums))